Triangulation refers to capturing a measurement target point by two calibrated cameras from different positions, and estimating optimum three-dimensional coordinates of the measurement target point from a point corresponding to the measurement target point (hereinafter simply referred to as a corresponding point) in each image. Calibrated means that an intrinsic parameter, such as a focal length and an optical center of each camera, and an extrinsic parameter, such as a position and an attitude of each camera, are known.
The optimum three-dimensional coordinates refer to a point at which a sum of squares of each distance between two-dimensional image coordinates obtained by projecting estimated three-dimensional coordinates onto each camera, and image coordinates of an observed corresponding point (hereinafter simply referred to as a reprojection error) is minimum. Obtaining a point at which a reprojection error is minimum is equivalent to obtaining a point at which each line passing through a center of each camera and a corresponding point intersects each other in a three-dimensional space. At this time, it is known that a relative geometric relation between the corresponding points and the respective cameras satisfies a constraint called an epipolar equation. When the corresponding points satisfy the epipolar equation, optimum three-dimensional coordinates can be obtained by a linear least squares method. However, an observed corresponding point contains an error due to influence of various types of noise such as a sensor, and therefore the epipolar equation is generally not satisfied, and three-dimensional coordinates estimated by the linear least squares method are not optimum.
A method called a bundle adjustment method is widely known as a common method for estimating three-dimensional coordinates. The bundle adjustment method estimates optimum three-dimensional coordinates by minimizing a reprojection error by an unconstrained nonlinear optimization method such as Levenberg-Marquardt method, with non-optimum three-dimensional coordinates obtained by a linear least squares method as initial values. For example, NPLs 1 and 2 describe methods of estimating initial values by a linear least squares method.
NPLs 3, 4, and 5 propose schemes of correcting coordinates of each corresponding point instead of directly optimizing three-dimensional coordinates. Specifically, coordinates of optimum corresponding points satisfying an epipolar equation are first obtained, and optimum three-dimensional coordinates are subsequently estimated by a linear least squares method. Then, in NPL 3, calculation of a globally optimum correction amount depends on a sixth-degree polynomial using single-variable.
It is known that the optimum correction amount is equivalent to a reprojection error. By contrast, in NPLs 4 and 5, a scheme of calculating a correction amount of each corresponding point by iteration of linear computations without solving a sixth-degree equation, by applying first-order approximation to an epipolar equation primarily being a quadratic expression, is proposed.